package algorithm.t202112;


import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/1 9:24
 * @description :6道
 * 22岁的第三天，力扣刷题满300。明天说是：《毕业实习动员暨毕业实习安排会》，我估计应该就和上一届一样是去西部云谷的微软实习两周ps-.-。唉，明天去确定下
 寒假去哪家厂实习，从2021年3月开学（大三下班学期）起，我就在很认真地度过每一天，用心去感受每一天的流逝，可是时间还是会走，谁也留不住，【握在手中却流逝于指缝】
 。每天都在提醒自己：努力，奋斗。人生路还有很长，我即将走出第一个阶段（学生阶段），进入到一个更长的阶段（成年人阶段），唉，确实，人只有在将要失去时才会加倍
 珍惜。
 persevere to last
 2021.12.1
 李红磊
 2021年12月1日21:12:18
 */
public class t20211201 {

    //1446.连续字符
    public int maxPower(String s) {
        return 0;
    }

    //83.删除排序链表中的重复元素
    public ListNode deleteDuplicates(ListNode head) {
        return null;
    }

    //309.最佳买卖股票时机含冷冻期
    public int maxProfit(int[] prices) {
        return 0;
    }

    //714.买卖股票的最佳时机含手续费
    public int maxProfit(int[] prices, int fee) {
        return 0;
    }

    //112.路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return true;
    }

    //230.二叉搜索树中第k小的元素
    private int ans = 0, cnt = 0;
    public int kthSmallest(TreeNode root, int k) {

        dfs(root, k);
        return ans;
    }
    private void dfs(TreeNode root, int k) {
        if (root == null) return;
        dfs(root.left, k);
        cnt++;
        if (cnt == k) {
            ans = root.val;
            return;
        }
        dfs(root.right, k);
    }

    public int kthSmallest2(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<>();

        search(root, list);
        Collections.sort(list, (x, y) -> y - x);
        return list.get(list.size() - k);

    }
    private void search(TreeNode root, List<Integer> list) {
        if (root == null) return;
        search(root.left, list);
        list.add(root.val);
        search(root.right, list);

    }

    public int kthSmallest3(TreeNode root, int k) {
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (--k == 0) return root.val;
            root = root.right;
        }
        return -1; // never
    }
    List<Integer> list = new ArrayList<>();
    public int kthSmallest4(TreeNode root, int k) {
        dfs(root);
        Collections.sort(list);
        return list.get(k - 1);
    }
    void dfs(TreeNode root) {
        if (root == null) return;
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }


    public static void main(String[] args) {
        t20211201 t20211201 = new t20211201();
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        root.left = node1;
        root.right = node2;
        System.out.println(t20211201.kthSmallest4(root, 1));
        ArrayDeque<Integer> queue=new ArrayDeque(){{addLast(1);}};
    }

}
